package niuke;

/**
 * description:
 * author:张腾
 * date:2021-07-12
 */

/**
 * 给出一个链表和一个值 ，以 为参照将链表划分成两部分，使所有小于 的节点都位于大于或等于 的节点之前。
 * 两个部分之内的节点之间要保持的原始相对顺序。
 * 例如：
 * 给出 1→4→3→2→5→2 和  x=3,
 * 返回 1→2→2→4→3→5.
 */
public class NC23 {
    //将小于x的都放在新的小链表，大于都放在新的大链表，最后合并
    public ListNode partition (ListNode head, int x) {
        // 创建哑节点和两个链表
        ListNode small = new ListNode();
        ListNode smallHead = small;
        ListNode large = new ListNode();
        ListNode largeHead = large;
        //对链表进行规则划分
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = small.next;
            }else{
                large.next = head;
                large =large.next;
            }
            head = head.next;
        }
        //对链表进行指空处理
        large.next = null;
        //将链表连起来
        small.next = largeHead.next;
        //返回新链表
        return smallHead.next;
    }
}
